home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 13845 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.4 KB  |  80 lines
  1. Newsgroups: comp.lang.c++
  2. Path: in2.uu.net!allegra!alice!ark
  3. From: ark@research.att.com (Andrew Koenig)
  4. Subject: Re: NEWBIE : Quicksort
  5. Message-ID: <Doxpq0.2t5@research.att.com>
  6. Organization: AT&T Research, Murray Hill NJ
  7. References: <4j4ruf$gf4@news1.h1.usa.pipeline.com> <Pine.SOL.3.91.960325221334.202B-100000@orion> <3159337A.2DB5@staff.ichange.com>
  8. Date: Wed, 27 Mar 1996 16:27:36 GMT
  9.  
  10. In article <3159337A.2DB5@staff.ichange.com> Jesse Liberty <jl@staff.ichange.com> writes:
  11.  
  12. > Sure, in my book Teach Yourself MORE C++ In 21 Days I show how to write a number of sorts, quicksort among them. Here's the 
  13. > basic code. 
  14.  
  15. >     template <class T>
  16. >     void myQuickSort(T* Input, int left, int right)
  17. >     {
  18. >        if (right > left)
  19. >        {
  20. >           T target = Input[right-1];
  21. >           int i = left-1;
  22. >           int x = right-1;
  23. >           for (;;)
  24. >           {
  25. >              while (*Input[++i] < *target)
  26. >              ;
  27. >              while (*Input[--x] > *target)
  28. >              ;
  29. > 
  30. >              if (i >= x)
  31. >                 break;
  32. >              Swap(Input[i], Input[x]);
  33. >           }
  34.  
  35. >           Swap(Input[i], Input[right-1]);
  36. >           myQuickSort(Input,left,i);
  37. >           myQuickSort(Input,i+1,right);
  38. > 
  39. >        }
  40. >     }
  41.  
  42. >     template <class T>
  43. >     inline void Swap(T& i, T& j)
  44. >     {
  45. >        T temp;
  46. >        temp = j;
  47. >        j = i;
  48. >        i = temp;
  49. >     }
  50.  
  51. I hope this isn't what's in the book.
  52.  
  53. For one thing, this code doesn't sort the elements of an array in the ordinary
  54. sense.  Rather, it sorts an array of pointers based on comparing the values
  55. to which the pointers point.  That is, the comparisons
  56.  
  57.     *Input[++i] < *target
  58.  
  59. and
  60.  
  61.     *Input[--x] > *target
  62.  
  63. require that type T be a pointer type, or at least a type on which unary *
  64. is defined.
  65.  
  66. There's nothing wrong with that, but it's a little surprising -- especially
  67. because that's *not* what the C or C++ library sort functions do.
  68.  
  69. Moreover, the algorithm as shown has a shortcoming that is common to many
  70. implementations of quicksort: if you give it an array that is already
  71. sorted, its execution time is quadratic in the number of elements.
  72.  
  73. I'm not aiming criticism at this book in particular, which I haven't read.
  74. What I'm trying to argue is that good algorithms are not easy to design,
  75. even when they appear simple.  Libraries are there for a reason, and you
  76. should use them whenever it makes sense.
  77. -- 
  78.                 --Andrew Koenig
  79.                   ark@research.att.com
  80.